package leetcode31_40;

import org.junit.Test;

import java.util.*;

/**
 * @author shhjiang_001
 * @create 2020-06-16 23:39
 */

       /*
        给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
        candidates 中的每个数字在每个组合中只能使用一次。
        说明：
        所有数字（包括目标数）都是正整数。
        解集不能包含重复的组合。
        示例 1:

        输入: candidates = [10,1,2,7,6,1,5], target = 8,
        所求解集为:
        [
        [1, 7],
        [1, 2, 5],
        [2, 6],
        [1, 1, 6]
        ]
        */

public class Solution40 {
    List<List<Integer>> resLists = new ArrayList<>();
    HashSet<String> set = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        method(candidates,target,0,new ArrayList<Integer>());
        return resLists;
    }

    private void method(int[] candidates, int target, int index, ArrayList<Integer> list) {
        if (target == 0){
            ArrayList<Integer> judgeList = new ArrayList<>(list);
            if (!set.contains(judgeList.toString())){
                set.add(judgeList.toString());
                resLists.add(new ArrayList<>(judgeList));
            }
        }
        for (int i= index;i < candidates.length;i++){
            if (target-candidates[i] >= 0){
                list.add(candidates[i]);
                method(candidates,target-candidates[i],i+1,list);
                list.remove(list.size()-1);
            }else {
                break;
            }
        }
    }
    @Test
    public void test() {
        Solution40 solution40 = new Solution40();
//        System.out.println(Arrays.asList(new int[]{1, 2, 3}).toString());
        solution40.combinationSum2(new int[]{10,1,2,7,6,1,5},8);
//        ArrayList<Integer> integers = new ArrayList<>();
//        integers.add(1);
//        integers.add(4);
//        integers.add(2);
//        integers.add(3);
//        Collections.sort(integers);
//        System.out.println(integers.toString());
    }
}
